# !/usr/bin/env python
# -*- coding: utf-8 -*-

# 计数排序
# 基本原理：
# 1.根据待排序集合中最大元素max和最小元素min的差值范围，创建临时数组，大小为max-min，
# 下标0表示min值,下标1表示min+1,下标max-min - 1表示max值,依次加一递增
# 2.遍历待排序集合，将每一个元素出现的次数记录到元素值对应的临时数组内；
# 3.遍历临时数组, 根据元素出现次数，几次则输出元素几次

# 使用场景： 只适用于正整数排序
# 时间复杂度: O(n + k)
# 空间复杂度: O(k)
# 稳定性: 稳定
from sort.arr_util import random_scale_arr


def count_sort(num_arr):
    min_num = min(num_arr)
    max_num = max(num_arr)
    num_dict = dict()
    for num in num_arr:
        val = num_dict.get(num)
        if val is None:
            num_dict[num] = 1
        else:
            num_dict[num] = val + 1
    count_arr = []
    for i in range(min_num, max_num + 1):
        val = num_dict.get(i)
        if val is None:
            val = 0
        count_arr.append(val)

    num_index = 0
    for i in range(min_num, max_num + 1):
        count = count_arr[i - min_num]
        k = 0
        while k < count:
            k += 1
            num_arr[num_index] = i
            num_index += 1


if __name__ == '__main__':
    arr = [1, 2, 5, 7, 6, 5, 4]
    count_sort(arr)
    print(arr)
    arr2 = random_scale_arr(20, 500)
    count_sort(arr2)
    print(arr2)
